#pragma once

#include <algorithm>
#include <array>
#include <utility>
#include <vector>

namespace sorting
{
    namespace impl
    {
        /* 将任意整数类型映射到 long long 进行安全计算 */
        template <typename T>
        using promote_t = typename std::conditional<
            std::is_unsigned<T>::value,
            unsigned long long,
            long long>::type;
    } // namespace impl

    /**
     * @brief   基数排序
     * @note    正负数都可以排，这里仅针对十进制数排序
     * @tparam  T       任何整数类型
     * @param   vec     待排序数组
     */
    template <typename T>
    typename std::enable_if<std::is_integral<T>::value>::type
    RadixSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        using std::array;
        using std::vector;
        using promote_t = impl::promote_t<T>;

        // 提升为更大类型，防止溢出
        vector<promote_t> tmp(vec.begin(), vec.end());

        // 偏移到非负，仅当类型是有符号类型且存在负数
        promote_t offset = 0;
        if (std::is_signed<T>::value)
        {
            const promote_t minval = *std::min_element(tmp.begin(), tmp.end());
            offset = -minval;
            for (auto &v : tmp)
            {
                v += offset;
            }
        }

        /* 3. 基数排序 */
        constexpr int base = 10;
        array<vector<promote_t>, base> buckets;

        const promote_t maxval = *std::max_element(tmp.begin(), tmp.end());
        for (promote_t exp = 1; maxval / exp > 0; exp *= base)
        {
            for (auto &v : tmp)
            {
                int digit = static_cast<int>((v / exp) % base);
                buckets[digit].push_back(v);
            }
            size_t idx = 0;
            for (auto &bucket : buckets)
            {
                for (auto v : bucket)
                {
                    tmp[idx++] = v;
                }
                bucket.clear();
            }
        }

        /* 4. 还原偏移 */
        if (std::is_signed<T>::value)
        {
            for (auto &v : tmp)
                v -= offset;
        }

        /* 5. 写回原向量 */
        std::copy(tmp.begin(), tmp.end(), vec.begin());
    }
} // namespace sorting
